In computational geometry and computer science, the minimum-weight triangulation (MWT) problem is the problem of finding a triangulation of minimal weight. Of particular interest is the problem of finding a minimum-weight point set triangulation.
Contents |
The weight of a triangulation of a set of points in the Euclidean plane is defined as the sum of lengths of its edges. The computational complexity of the problem of finding an MWT for a planar point set used to be one of the long-standing open problems listed in the seminal book Computers and Intractability by Garey and Johnson. Its decision variant, i.e., the problem of deciding whether there exists a triangulation of weight less than a given weight, was proven to be NP-hard in 2006 by W. Mulzer and G. Rote. Their proof is by reduction from the PLANAR-1-IN-3-SAT[1] problem.[2]
It is not known whether it is NP-complete, since this depends on the known open problem whether the sum of radicals may be computed in polynomial time. Mulzer and Rote remark that the problem is NP-complete if the edge weights are the rounded lengths. Their result also implies the NP-hardness of finding an approximate solution with relative approximation error at most O(1/n2).
A polygon triangulation of minimal weight may be constructed in cubic time using the dynamic programming approach, reported independently by Gilbert (1979) [3] and Klincsek (1980)[4].